#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class app_t 
{
public:
    app_t(int s, int e) : start(s), end(e), hasConflict(false){}
    app_t(){};
    int start, end;
    bool hasConflict;
};

class point_t 
{
public:
    point_t(int d, bool start, app_t *s): data(d), isStart(start), seg(s){}
    int data;
    bool isStart;
    app_t *seg;
};

bool mycomp(const point_t lhs, const point_t rhs)
{
    return lhs.data < rhs.data;
}


int main(int argc, char **argv)
{
    vector<app_t *> apps;
    vector<point_t> points;

    apps.push_back(new app_t(1,6));
    apps.push_back(new app_t(7,13));
    apps.push_back(new app_t(8,16));
    apps.push_back(new app_t(12,26));
    apps.push_back(new app_t(31,46));
    apps.push_back(new app_t(51,56));
    
    for (int i = 0; i < apps.size(); i++) {
	points.push_back(point_t(apps[i]->start, true, apps[i]));
	points.push_back(point_t(apps[i]->end, false, apps[i]));
    }
    sort(points.begin(), points.end(), mycomp);
   
    for (int i = 0; i < points.size(); i++)
	cout << points[i].data << " ";
    cout << endl; 

    int stack = 0;
    for (int i = 0; i < points.size(); i++) {
	if (points[i].isStart) {
	    if (stack > 0) 
		points[i].seg->hasConflict = true;
	    stack++;
	} else {
	    stack--;
	    if (stack > 0) 
		points[i].seg->hasConflict = true;
	}
    }
    for (int i = 0; i < apps.size(); i++)  {
	if (apps[i]->hasConflict) cout << "hasConflict:";
	cout << apps[i]->start << " " << apps[i]->end << endl;
    }

}
